package Demo1_31;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-01-31
 * Time:22:05
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class SubtreeOfAnotherTree {
    // 主方法，用于检查 root 中是否包含 subRoot 子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        // 先检查当前节点为根的子树是否和 subRoot 相同
        if (isSameTree(root, subRoot)) {
            return true;
        }
        // 递归检查左子树和右子树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    // 辅助方法，用于判断两棵树是否完全相同
    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        // 当前节点值相同，并且左子树和右子树都相同
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    public static void main(String[] args) {
        // 构建 root 树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(4);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(2);

        // 构建 subRoot 树
        TreeNode subRoot = new TreeNode(4);
        subRoot.left = new TreeNode(1);
        subRoot.right = new TreeNode(2);

        SubtreeOfAnotherTree solution = new SubtreeOfAnotherTree();
        boolean result = solution.isSubtree(root, subRoot);
        System.out.println("root 中是否包含 subRoot 子树: " + result);
    }
}